#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long
using namespace std;
template<class T,class U,int N>struct EK{
    const T Tinf=numeric_limits<T>::max()/2;
    const U Uinf=numeric_limits<U>::max()/2;
    int n,m,s,t,pv[N],pe[N];bool hav_neg;U D[N],H[N];
    vector<tuple<int,T,U,int>>G[N];
    inline void add(const int&u,const int&v,const T&w,const U&c){
        const int ru=G[v].size()+(u==v),rv=G[u].size();
        G[u].emplace_back(v,w,c,ru),G[v].emplace_back(u,0,-c,rv),hav_neg|=(c<0),++m;
    }
    inline bool dij(){
        fill(D+1,D+n+1,Uinf),D[s]=0;
        if(2ll*m*__lg(m+1)<1ll*n*n){
            priority_queue<pair<U,int>>Q;
            for(Q.emplace(0,s);!Q.empty();){
                auto [du,u]=Q.top();Q.pop();
                if(D[u]!=-du)continue;
                for(auto [v,w,c,_]:G[u])if(w&&D[v]>D[u]+c+H[u]-H[v])
                    D[v]=D[u]+c+H[u]-H[v],pv[v]=u,pe[v]=_,Q.emplace(-D[v],v);
            }
        }
        else{
            static bool inq[N];
            for(;;){
                int u=0;
                for(int i=1;i<=n;++i)if(!inq[i]&&(!u||D[i]<D[u]))u=i;
                if(!u)break;inq[u]=1;
                for(auto [v,w,c,_]:G[u])if(w&&D[v]>D[u]+c+H[u]-H[v])
                    D[v]=D[u]+c+H[u]-H[v],pv[v]=u,pe[v]=_;
            }
            fill(inq+1,inq+n+1,0);
        }
        return D[t]<Uinf;
    }
    inline bool spfa(){
        fill(D+1,D+n+1,Uinf);
        queue<int>Q;static bool inq[N];
        for(D[s]=0,Q.push(s);!Q.empty();){
            int u=Q.front();Q.pop(),inq[u]=0;
            for(auto [v,w,c,_]:G[u])if(w&&D[v]>D[u]+c+H[u]-H[v]){
                D[v]=D[u]+c+H[u]-H[v],pv[v]=u,pe[v]=_;
                if(!inq[v])Q.push(v),inq[v]=1;
            }
        }
        return D[t]<Uinf;
    }
    inline void init(const int&_n,const int&_s,const int&_t){
        n=_n,m=0,s=_s,t=_t,hav_neg=0;
        for(int i=1;i<=n;++i)G[i].clear(),H[i]=0;
    }
    inline pair<T,U>flow(LL* cost){
        T z=0;U r=0;
        if(hav_neg?spfa():dij())do{
            for(int i=1;i<=n;++i)H[i]+=D[i];
        	T mf=Tinf;
			for(int i=t;i!=s;i=pv[i])mf=min(mf,get<1>(G[pv[i]][get<3>(G[i][pe[i]])]));
			for(int i=t;i!=s;i=pv[i])get<1>(G[pv[i]][get<3>(G[i][pe[i]])])-=mf,get<1>(G[i][pe[i]])+=mf;
			z+=mf,r+=mf*H[t],(*++cost)=r;
        }while(dij());
        return make_pair(z,r);
    }
};
const int N=305,INF=1e9;
int n,m,q,G[N][N],H[N][N];LL pre[N];
EK<int,LL,N*2>Gr;
signed main(){
    cin.tie(0)->sync_with_stdio(0);
	freopen("journey.in","r",stdin);
	freopen("journey.out","w",stdout);
	cin>>n>>m>>q;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			G[i][j]=INF;
	for(int i=1;i<=m;++i){
		int u,v,w;cin>>u>>v>>w;
		G[u][v]=min(G[u][v],w);
	}
	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
	Gr.init(n*2+2,n*2+1,n*2+2);
	for(int i=1;i<=n;++i)Gr.add(Gr.s,i,1,0),Gr.add(i+n,Gr.t,1,0);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			Gr.add(i,j+n,1,G[i][j]);
	Gr.flow(pre);
	for(int _=1;_<=q;++_){
		int C;LL ans=INF;cin>>C;
		for(int i=0;i<=n;++i)ans=min(ans,pre[i]+(n-i)*C);
		cout<<ans<<'\n';
	}
    return 0;
}
/*
x*y
*/